class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        // 所有负数都设置成 n+1
        for (int i = 0; i < n; i++){
            if (nums[i] <= 0){
                nums[i] = n+1;
            }
        }
        // 遍历到的正数都置为负
        for (int i = 0; i < n; i++){
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num-1] = -Math.abs(nums[num-1]);
            }
        }
        // 遍历，正元素就是缺失的，返回最小的那个
        for (int i = 0; i < n; i++){
            if (nums[i] > 0) {
                return i+1;
            }
        }
        return n+1;
    }


    public int firstMissingPositive1(int[] nums) {
        int n = nums.length;
        
        // 将元素x置换到x-1处
        for (int i = 0; i < n; i++){
            // 排除两处位置相同的元素
            while (nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i]) {
                int tmp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = tmp;
            }
        }
    
        // 遍历，正元素就是缺失的，返回最小的那个
        for (int i = 0; i < n; i++){
            if (nums[i] != i+1) {
                return i+1;
            }
        }
        return n+1;
    }
}